package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 1201. 丑数 III
 *
 * @author liw
 * @version 1.0
 * @date 2022/3/26 21:13
 */
public class NthUglyNumber {

    public static void main(String[] args) {
        NthUglyNumber test = new NthUglyNumber();

        // 5
        int n = 4;
        int a = 2;
        int b = 3;
        int c = 5;

        // 6
//        int n = 4;
//        int a = 2;
//        int b = 3;
//        int c = 4;

        // 1999999984
//        int n = 1000000000;
//        int a = 2;
//        int b = 217983653;
//        int c = 336916467;

        int i = test.nthUglyNumber(n, a, b, c);
        System.out.println(i);
    }

    public int nthUglyNumber(int n, int a, int b, int c) {
        long st = 0;
        long end = Integer.MAX_VALUE;
        while (st <= end) {
            long m = st + ((end - st) >> 1);
            long l = find(m, a, b, c);
            if (l > n) {
                end = m - 1;
            } else if (l < n) {
                st = m + 1;
            } else {
                if (m % a == 0 || m % b == 0 || m % c == 0) {
                    return (int) m;
                } else {
                    end = m - 1;
                }
            }
        }
        return -1;
    }

    private long find(long m, long a1, long b1, long c1) {
        long l = a1 * b1 / find(a1, b1);
        long t = m / a1 + m / b1 + m / c1;
        long t2 = m / l + m / (b1 * c1 / find(b1, c1)) + m / (a1 * c1 / find(a1, c1));
        long t3 = m / (l * c1 / find(l, c1));
        return (int) (t - t2 + t3);
    }

    private long find(long a, long b) {
        if (b == 0) {
            return a;
        }
        return find(b, a % b);
    }

}
